package implementations;
import java.util.Random;


public class RandomQuickSort {

    private static Random random = new Random();

    public static int[] QuickSort(int[] array){
        quick(array,0,array.length - 1);
        return array;
    }

    private static void quick(int[] array,int bot, int top){
        if(bot >= top){
            return;
        }

        int partition = partition(array,bot,top);

        quick(array,bot,partition-1);
        quick(array,partition + 1, top);
    }

    private static int partition(int[] array, int bot, int top) {
        int number = random.nextInt((top-bot)+1) + bot;
        int pivot = array[number];
        swap(array,bot,number);

        int i = bot + 1;
        int j = top;
        while(i <= j){
            if(array[i] <= pivot){
                i++;
            }else if (array[j] >= pivot){
                j--;
            }else{
                swap(array,i,j);
            }
        }

        swap(array,j,bot);
        return j;
    }

    private static  void swap(int[] array, int a, int b){
        int aux = array[a];
        array[a] = array[b];
        array[b] = aux;
    }
}